package 算法.leetcode.labuladong.数组和链表;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author lchenglong
 * @date 2022/6/21
 */
public class 滑动窗口最大值 {
    static class Solution {


        public int[] maxSlidingWindow(int[] nums, int k) {
            MonotonyQueue window = new MonotonyQueue();
            List<Integer> ans = new ArrayList<>();
            for (int i=0;i<nums.length;i++){
                if (i<k-1){
                    // 先把窗口的前K-1个元素填充
                    window.push(nums[i]);
                } else {
                    // 窗口第一个元素
                    window.push(nums[i]);
                    // 窗口开始后移
                    ans.add(window.max());
                    // 移除窗口的最后一个元素
                    window.pop(nums[i-k+1]);
                }
            }
            int[] res = new int[ans.size()];
            for (int i=0;i<res.length;i++){
                res[i] = ans.get(i);
            }
            return res;
        }
        // 单调队列
        class MonotonyQueue {
            LinkedList<Integer> queue = new LinkedList<>();
            // 取最大值
            public Integer max(){
                return queue.getFirst();
            }

            public void push(int value){
                while (!queue.isEmpty()&&queue.getLast()<value){
                    // 把比自己小的都移出去
                    queue.pollLast();
                }
                queue.addLast(value);
            }

            public void pop(int n){
                if (n == queue.getFirst()){
                    // 如果是最大的值 那就移除,否则在push的时候也会移除
                    queue.pollFirst();
                }
            }
        }
    }
}
